Batch 3 - Class 230 - Information and Compression

• (Moscow - 197) A complete set of dominos is as shown below. If you place all the 28 tiles in a continuous chain (adjacent ends of the tiles must match) so that 5 dots are at one end, how many dots will be at the other end?

• Get kids to think about a piece of information, and different ways of expressing it. Example: how would you express a "teacher"? Could do that by writing "teacher", drawing a teacher, dumb charades, photo of a teacher, saying "teacher", etc. Hence, motivate the fact that ways of expression (including language) are different from the underlying information, which might be the same. Let kids play with other expressions.
• Pictogram - represent a concept by pictures. For example: "Half way up the river towards the west" - let kids do this. Then let teams communicate the same idea to their team mates using pictures, and see who does it first.
• Illustrate evolution of language from pictures as a more efficient and reliable means of communication - to communicate the same information

• Game of 20 questions
• How many possible answers can be covered? (back to binary math)
• What should successive questions do? Should the first question be broad or narrow? ("Male living?" versus "Abraham Lincoln?")
• Encoding letters using 0 and 1
• Suppose you had to be able to communicate the roll of two dice with 0s and 1s. Devise a scheme to do that. How many binary characters do you need?
• How many "bits" are required for all alphabets? What if we wanted small and upper case? What if we wanted to leave some out for special characters, space, etc?
• ASCII code - 7 digit encoding of english language alphabets
• Role of a keyboard on a computer

• Exercise: If I have a binary mode of communication, how should I charge for the following messages
• result of 10 coin flips
• a six letter word
• a poker hand (set of 5 cards from a deck)

• What if we dont have two signals but only one. Like a bulb which can be on or off. 
• We could pluck the string as many number of times as the character number
• Or, we could create more signals out of one - as in morse code - can get to any character in up to 5 plucks.
• Show parallel to binary coding, with dots being zeros and dashes being ones

• Dynamic Encoding - Take an example of sending outcome of two dice rolls through plucks on a wire. Base case: 1 is one pluck, 2 is two plucks and so on. What is average number of plucks needed? How can you improve the coding?
• Insight: Coding can be made more efficient by choosing the shortest codes for most common signals.
• How can this be applied to coding letters of english alphabet?

• Go back to Morse code, and let kids figure out the correlation between character frequency and morse code (Example: E is the shortest) - try http://www.braingle.com/brainteasers/codes/morse.php to create your own message
• What if you wanted to code it without using spaces (which morse code uses) - introduce notion of coding without repeating prefixes
• Role of teletypewriters in transmitting messages
• Telephone numbers, and STD and ISD codes - what are the assumptions in this design with respect to frequency of calling? How does the system know whether we are dialing local or STD? (notion of non-repeating prefix again)
• Assimilate: Dynamic coding essentially leads to compression - which means that the same message can be sent in fewer "bits".
• Huffman coding - tree method
• Develop huffman coding for roll of two dice - average length of code is 3.3056

• For sequence of letters  https://www.youtube.com/watch?v=co4_ahEDCho - note the need to transmit the coding scheme itself if we are going to change the scheme by each message
• Dynamic Huffman Coding builds this tree on the fly as characters appear. So there is no apriori knowledge of probabilities. The coding for the same character may change as more symbols appear.

• (AOPS) Count number of trailing zeros in 320! 
• Answer: 78 (The key insight is that every 5 as a factor yields a trailing zero in the factorial product (when added to an even number, of which there are enough available in the factorial product). Thus there are 320/5=64 multiples of 5. The multiples of 25 give two zeros, and hence need to be added - there are 320/25=12 of these. The multiples of 125 give 3 zeros, and hence need to add those - there are two of those. Total 64+12+2=78)